Online election

Time: CTOR:O(N), Query:O(LogN); Space: O(N); medium

In an election, the i-th vote was cast for persons[i] at time times[i].

Now, we would like to implement the following query function:

  • TopVotedCandidate.q(int t)

will return the number of the person that was leading the election at time t.

Votes cast at time t will count towards our query.

In the case of a tie, the most recent vote (among tied candidates) wins.

Example 1:

Input/Output:

  • persons = [0,1,1,0,0,1,0]

  • times = [0, 5, 10, 15, 20, 25, 30]

  • s = TopVotedCandidate(persons, times)

  • s.q(3) -> 0

  • s.q(12) -> 1

  • s.q(25) -> 1

  • s.q(15) -> 0

  • s.q(24) -> 0

  • s.q(8) -> 1

Explanation:

  • At time 3, the votes are [0], and 0 is leading.

  • At time 12, the votes are [0,1,1], and 1 is leading.

  • At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)

  • This continues for 3 more queries at time 15, 24, and 8.

Constraints:

  • 1 <= len(persons), len(times) <= 5000

  • 0 <= persons[i] <= len(persons)

  • times is a strictly increasing array with all elements in [0, 10^9].

  • TopVotedCandidate.q is called at most 10000 times per test case.

  • TopVotedCandidate.q(int t) is always called with t >= times[0].

1. Binary Search (List of Lists) [O(N+QLogN), O(N)]

Intuition and Algorithm

We can store the votes in a list A of lists of votes. Each vote has a person and a timestamp, and A[count] is a list of the count-th votes received for that person.

Then, A[i][0] and A[i] are monotone increasing, so we can binary search on them to find the most recent vote by time.

[1]:

import bisect
import collections

class TopVotedCandidate1(object):
    """
    Time: O(N+QLogN), where N is the number of votes, and Q is the number of queries.
    Space: O(N)
    """
    def __init__(self, persons, times):
        """
        :type persons: List[int]
        :type times: List[int]
        """
        self.A = []
        self.count = collections.Counter()

        for p, t in zip(persons, times):
            self.count[p] = c = self.count[p] + 1
            while len(self.A) <= c:
                self.A.append([])
            self.A[c].append((t, p))

    def q(self, t):
        lo, hi = 1, len(self.A)
        while lo < hi:
            mi = (lo + hi) // 2
            if self.A[mi][0][0] <= t:
                lo = mi + 1
            else:
                hi = mi
        i = lo - 1
        j = bisect.bisect(self.A[i], (t, float('inf')))
        return self.A[i][j-1][1]

[2]:

persons = [0, 1, 1, 0, 0, 1, 0]
times = [0, 5, 10, 15, 20, 25, 30]

s = TopVotedCandidate1(persons, times)

assert(s.q(3)) == 0
assert(s.q(12)) == 1
assert(s.q(25)) == 1
assert(s.q(15)) == 0
assert(s.q(24)) == 0
assert(s.q(8)) == 1

2. Binary Search (Precomputed Answer) [O(N + QLogN), O(N)]

Intuition and Algorithm

As the votes come in, we can remember every event (winner, time) when the winner changes. After, we have a sorted list of these events that we can binary search for the answer.

[3]:

import collections
import bisect

class TopVotedCandidate2(object):
    """
    Time: O(N+QLogN), where N is the number of votes, and Q is the number of queries.
    Space: O(N)
    """
    def __init__(self, persons, times):
        """
        :type persons: List[int]
        :type times: List[int]
        """
        lead = -1
        self.A, count = [], collections.defaultdict(int)

        for t, p in zip(times, persons):
            count[p] += 1
            if count[p] >= count[lead]:
                lead = p
                self.A.append((t, lead))

    def q(self, t):
        """
        :type t: int
        :rtype: int
        """
        i = bisect.bisect(self.A, (t, float('inf')), 1)
        return self.A[i-1][1]

[4]:

persons = [0, 1, 1, 0, 0, 1, 0]
times = [0, 5, 10, 15, 20, 25, 30]

s = TopVotedCandidate2(persons, times)

assert(s.q(3)) == 0
assert(s.q(12)) == 1
assert(s.q(25)) == 1
assert(s.q(15)) == 0
assert(s.q(24)) == 0
assert(s.q(8)) == 1